Test 2019.8.11 题解

题目传送门

T1 T2 T3 T4

---

题解

T1 买鸡

这道题题面较为简单，很容易想到无脑暴力。打着 三维 的暴力，嘴里哼着小曲，一切会体面，woc数据范围有 20000 ！！！转念一想，觉得还是有很大优化空间的，于是三维的暴力就成了二维的n方暴力，代码如下。

#include<bits/stdc++.h>
#define re register int
using namespace std;
int n,m,s1,s2,t;
int main(){
	scanf("%d%d",&m,&n);   //输入，ps:本人在此将m当成钱，n当成只数.
	for(re i=0;i<=n;i++){     //枚举过程，从0只公鸡枚举到n只公鸡.
		s1=i*5;    //买i只公鸡所花的钱
		for(re j=0;j<=n;++j){   //从0只母鸡枚举到n只母鸡.
			s2=j*3;    //买i只母鸡所花的钱.
            t=(m-s1-s2)*3;    //m-s1-s2是剩下的钱，因为一元钱可以买三只鸡，所以乘3.
			if(t+i+j==n)printf("%d %d %d\n",i,j,t);//如果买的鸡数等于题目要求数，输出
		}
	}
	return 0;
}

没有优化的还是比较简单无脑的

但是，有的 DL 就会提出疑问了，n方的复杂度，20000不是也会超时吗？

正确！

当 i 为 k 时，j 能取的最大值为 n-k.

所以我们还可以优化 j 循环的次数，在数据较大时能砍下不少常数. (浪费时间)

得到以下伪代码:

for(i=0;i<=n;++i){
    for(j=0;j<=n-i;++j){  //优化为n-i
    	····
    }
}

很多人以为这样就优化完了，实则不然，再细看题面，发现还可以优化，在 i 循环的过程中，可以将循环的最大值设为 min(m/5,n) ,为什么呢？因为m为钱,一只公鸡需要5元，那么最多买的公鸡数则为m/5 (ps:买不起)。同理，j也是如此。

最终得到以下代码（仅供参考）

#include<bits/stdc++.h>
#define re register int
using namespace std;
int n,m,s1,s2,s3,t;
int main(){
	scanf("%d%d",&m,&n);
	for(re i=0;i<=min(m/5,n);++i){
		s1=i*5;
		for(re j=0;j<=min(m-i*5,n-i);++j){
			s2=j*3;t=(m-s1-s2)*3;
			if(t+i+j==n)printf("%d %d %d\n",i,j,t);
		}
	}
	return 0;
}

---

T2 勾股数

本人目前能力有限，还暂时不会订正，先放一下本人的暴力代码。

#include<bits/stdc++.h>
#define re register int
#define fly(a,b,c) for(re a=b;a<=c;a++)
using namespace std;
int r,k;
long long s1,s2,ans;
int check(long long n){
	if(sqrt(n)*sqrt(n)==n)return 1;
	else return 0;
}
int main(){
	scanf("%d",&r);
	fly(i,1,r){
		s1=i*i;
		fly(j,i,r){
			s2=j*j;
			if(check(s1+s2)){
				++j,++ans,k=sqrt(s1+s2);
				printf("%d %d %d\n",i,j,k);
			}
		}
	}
	printf("%d",ans);
	return 0;
}

---

T3 ISBN码

em,与洛谷的一道题目有些相似:传送门

一道超简单的字符串模拟，就是处理有点繁琐而已。

1.读入，获取字符长度 （等于没说）

2.按照ISBN的顺序求一个sum，记录”?”的出现位置

3.枚举

4.特判

#include<bits/stdc++.h>
#define re register int
#define r (10-i)
using namespace std;
char s[39];
int sum,l,p,k[39];
int main(){
	freopen("isbn.in","r",stdin);
	freopen("isbn.out","w",stdout);
	cin>>s,l=strlen(s);
	for(re i=0;i<l;i++){
		if(s[i]!='X'&&s[i]!='?')k[i+1]=(s[i]-'0')*r,sum+=k[i+1];
		else if(s[i]=='?')p=i;
		else if(s[i]=='X')k[i+1]=10*r,sum+=k[i+1];
	}
	for(re i=0;i<=10;i++){
		if((sum+i*(10-p))%11==0&&i!=10){
			printf("%d",i);
			return 0;
		}
	}
	if(p==9)printf("X");
	else printf("-1");
	return 0;
}

---

T4 对角线

一道十分简单的模拟题，首先打出横竖两行应该是很简单的：

scanf("%d%d%d",&n,&x,&y);
FLY(i,1,n)printf("(%d,%d)",x,i);
FLY(j,1,n)printf("(%d,%d)",j,y);
//（注:FLY是自己码风的问题，总的来说是for(register int a=b;a<=c;a++)）

然后斜着两条略有一点难度,我的做法挺简单，但码量有点大

xx=x,yy=y;
while(xx>1&&yy>1){--xx;--yy;}

首先用 xx,yy 来定位(x,y),接着往左上方搜，如果到了对角线的顶点，就停止记录，接着是输出：

while(xx<=n&&yy<=n){printf("(%d,%d)",xx++,yy++);}

同理可得另外一条斜边的代码：

while(xx<n&&yy>1){++xx;--yy;}
while(xx>0&&yy<=n){printf("(%d,%d)",xx--,yy++);}

-------------本文结束感谢您的阅读-------------

本文作者： jfy
本文链接： http://example.com/2019/08/11/Test%202019.8.11/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

---

---

赏

谢谢你请我吃糖果